OS course

OS case study
OS Impl
Problems
- 下列几种关于进程的叙述中，最不符合操作系统对进程理解的是_____。 A．进程是在多程序并行环境中的完整的程序 B．进程可以由程序，数据和进程控制块描述 C．线程(Thread)是一种特殊的进程 D．进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位
- 当一个进程处于_____的状态时，称其为等待状态 A．它正等待调度 B．它正等着协作进程的一个消息 C．它正等分给它一个时间片 D．它正等进入内存
- 下列选项中，不可能在用户态发生的事件是（）。 A．系统调用 B. 外部中断 C. 进程切换 D. 缺页 12
- {:height 312, :width 448}
- 由于响应时间为作业进入系统后的等待时间加上估计运行时间。因此响应比＝1＋作业等待时间/估计运行时间响应时间：从提交请求到系统首次产生响应所用的时间。响应时间==周转时间？?
- 若某单处理器多进程系统中有多个就绪进程，则下列关于处理机调度的叙述中，错误的是（）12 A．在进程结束时能进行处理机调度 B．创建进程后能进行处理机调度 C．在进程处于临界区时不能进行处理机调度 D．在系统调用完成并返回用户态时能进行处理机调度
- 采用 _____ 不会产生内部碎片。 A.分页存储管理 B.固定分区存储管理 C.分段存储管理 D.段页式存储管理
- 把作业地址空间使用的逻辑地址变成内存的物理地址称为 _____ 。 A.加载 B.重定位 C.物理化 D.逻辑化
- 帧数为n时未换出的内存页集合是帧数为n+1的页集合的子集
- 利用率只有59%但每个进程的任务执行加起来就需要80%
- Bernstein条件
- 会产生Belady异常现象的页面置换算法是_____。 A．最佳页面置换算法 B．先进先出页面置换算法 C．最近最久未使用置换算法 D．最少使用页面置换算法
- 设备安全分配、不安全分配
- 在下面关于设备属性的论述中，正确的论述是_____。　 A．字符设备的一个基本特征是可寻址的。 B．共享设备必须是可寻址的和可随机访问的设备。 C．共享设备是指在同一时刻，允许多个进程同时访问的设备。（一段时间） D．在分配共享设备和独占设备时，都可能引起进程死锁。
- lock（w） { while（w==1）； w = 1； } 并行时会出错？

Linked References (7)

LRU impl methods
- counter: shift
- special stack: can adjust element’s pos in stack
- approximation: fewer bits
- second-chance: derived from FIFO, two stage phase out, a state bit
- clock: improved second-chance, using pointer over a ring queue
- improved clock: using ref,dirty bit
page buffering algorithm
- free FIFO, modified FIFO
- batch write back when modified blocks reached a threshold(batch write cost less than separate)
Frame Allocation
- DONE min frames required? :LOGBOOK: CLOCK: [2022-11-11 Fri 15:23:33] :END:
- strategies: equal, proportional, priority
- fixed versus mutable, global versus local
  - dynamic+local: monitoring page fault rate
- thrashing: most time spent on swapping in/out
  - causes: lack of frames, bad replacement algo, global replacement
  - working set model
  - detection: L=S, fault rate, replace speed
  - prevention: local replacement, working set, suspend some process
Others
- prepaging
- page size
  - tradeoffs: page table size, internal fragmentation, page load time(no big difference), locality
  - hardware: power of 2, 512B~16M
- TLB reach
  - page size variants(huge page)
- segmentation and hybrid
File System
- attributes: name, type, size, priviledge

Paging
- page table
  - valid bit: whether corresponding page belongs to the proc
  - object sharing
    
    reentrant code: non-self-modifying code
  - hierarchical
  - hashed
  - inverted
- segmentation
- hybrid
  - work->sections->pages
Virtual memory
- fundation: locality
- page table attrs
  - valid bit
  - dirty bit
  - access stat
- CoW
- page replacement select page to swap out
  - motivating example: same page swapped between code and data repeatedly
  - exception: more frames=>more faults
  - naive FIFO (may occur exception)
  - optimal: longest future use
  - LRU(approximating optimal): not used for longest time
  - LFU: frequency

TODO preemptive vs non-preemptive, any syscall? #OS course :LOGBOOK: CLOCK: [2022-11-04 Fri 15:46:28] CLOCK: [2022-11-04 Fri 15:46:30] :END:

OS course

memory allocation
- single partition
- fixed
  - pre-configured, runtime immutable, low efficiency
- naive dynamic
  - first-fit: naive, ordered by address
  - next-fit: ordered by address loopback
  - best-fit: ordered by cap ascending
  - worst-fit: ordered by cap descending
  - recycle
    
    three cases
  - defragmentation
    
    internal(in proc space), external(spare)
    
    compact
    
    need dynamic relocation
    
    where to put & when to compact
- friend algorithm
  - used in paging
Paging
- physical frames, logical pages
- page table
- frame table
  - record physical frame usage
  - bitmap / linked-list

DONE do until chapter7 #homework #OS course DEADLINE: <2022-11-04 Fri> :LOGBOOK: CLOCK: [2022-10-27 Thu 23:01:48]—[2022-11-11 Fri 16:20:38] => 353:18:50 :END:

OS course

Deadlock
- Prevention
  - Atomic Request
    
    request/assign resources at once
  - Circular Wait
    
    id-monotonic request per program
- Avoiding
  - Dynamic check on allocation, keep in safe state
    
    银行家算法
    
    claim max demand
    
    work(available), need, alloc
- Judgement
  - 死锁定理
    
    S is deadlock state $\iff$ RAG can’t be deduced
    
    prog->res => request, res->prog => alloc
- Diagnostics
  - Termination
    
    abort all
    
    abort one once and judge
  - Preemption
    
    select a victim, rollback, avoid starvation
Memory
- address binding
  - absolute addr
  - relocatable object
    
    PIC/PIE
    
    DONE static relocation :LOGBOOK: CLOCK: [2022-10-21 Fri 15:58:37]—[2022-10-23 Sun 00:25:49] => 32:27:12 CLOCK: [2022-10-23 Sun 00:26:07]—[2022-10-27 Thu 23:00:02] => 118:33:55 :END:
    
    relocate on startup
  - dynamic relocation
    
    relocate at runtime, hardware support(MMU)
    
    partial load/dynamic loading
- linking
  - static linking
  - dynamic linking
    
    stub 存根: entry to loaded module
    
    link on startup, or postpone to runtime
- swap
- mapping and protection :LOGBOOK: CLOCK: [2022-10-21 Fri 16:23:36] CLOCK: [2022-10-21 Fri 16:23:39] :END:
  - boundary register
    
    lower-upper register
    
    base-length register
  - DONE 存储保护键? :LOGBOOK: CLOCK: [2022-10-21 Fri 16:35:19]—[2022-10-27 Thu 22:48:59] => 150:13:40 :END:
    
    each block has a key-pair, only who has the key can access(impl using a special register)
  - ring protect
    
    access privileges r/w/(x), usually four combinations: non,ro,rw,rw

OS course